﻿///https://leetcode.cn/problems/minimum-window-substring/description/
class Solution {
public:
    string minWindow(string s, string t) {
        int hash1[128];
        int hash2[128];
        int kinds = 0;
        for (auto& str : t)//统计字符串 t 中每⼀个字符的频次
            if (hash1[str]++ == 0)
                kinds++;//有效字符种类
        int len = INT_MAX;
        int begin = -1;
        //count为有效字符的种类
        for (int left = 0, right = 0, count = 0; right < s.size(); right++) {
            char in = s[right];
            if (++hash2[in] == hash1[in])
                count++;
            while (kinds == count) {
                if (right - left + 1 < len) {
                    len = min(len, right - left + 1);
                    begin = left;
                }
                char out = s[left++];

                if (hash2[out]-- == hash1[out])
                    count--;
            }
        }
        return begin == -1 ? "" : s.substr(begin, len);
    }
};